import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/23 9:49
 * @description:
 */
public class Solution395 {
    public int longestSubstring(String s, int k) {
        int res = 0;
        for (int i = 1; i <= 26; i++) {
            res = Math.max(res, longestKLetterSubstr(s, k, i));
        }
        return res;
    }

    /**
     * 求每个字符都出现至少 k 次，仅包含 count 种不同字符的最长子串。
     *
     * @param s
     * @param k
     * @param count
     * @return
     */
    int longestKLetterSubstr(String s, int k, int count) {
        int left = 0;
        int res = 0;
        Map<Character, Integer> map = new HashMap<>();
        Set<Character> notValid = new HashSet<>();
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            map.put(c, map.getOrDefault(c, 0) + 1);
            if (map.get(c) < k) {
                notValid.add(c);
            } else {
                notValid.remove(c);
            }
            while (map.keySet().size() > count) {//核心注意点key要移除
                char letter = s.charAt(left);
                map.put(letter, map.get(letter) - 1);
                if (map.get(letter) < k && map.get(letter) != 0) {
                    notValid.add(letter);
                } else {
                    notValid.remove(letter);
                }
                if (map.get(letter) == 0) {
                    map.remove(letter);
                }
                left++;
            }
            if (notValid.isEmpty() && map.keySet().size() == count) {
                res = Math.max(res, right - left + 1);
            }
        }
        return res;
    }

    public int longestSubstring2(String s, int k) {
        if (s.length() < k) {
            return 0;
        }
        Map<Character, Integer> countMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            countMap.put(s.charAt(i), countMap.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (char c : countMap.keySet()) {
            if (countMap.get(c) < k) {
                int res = 0;
                for (String t : s.split(String.valueOf(c))) {
                    res = Math.max(res, longestSubstring2(t, k));
                }
                return res;
            }
        }
        return s.length();
    }

    public static void main(String[] args) {
        Solution395 solution = new Solution395();
        System.out.println(solution.longestSubstring("aaabb", 3));//3
        System.out.println(solution.longestSubstring("ababbc", 2));//5
        System.out.println(solution.longestSubstring("bbaaacbd", 3));//3
    }
}
